import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;

import java.util.Iterator;

import org.graphstream.graph.Edge;
import org.graphstream.graph.Element;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;
import org.graphstream.graph.implementations.DefaultGraph;


public class Prim {

	public Graph runPrim(Graph g)
	{
		/*Node inicial = g.getNode(0);
		for(Node n : g.get)
		for(Edge e : inicial.getEdges())*/
		Graph gPrim = new DefaultGraph("gPrim");
		int minW;
		Node targetNode = null;
		Node actualNode = null;
		Edge selectedEdge = null;
		ArrayList<Node> Q = new ArrayList<Node>();
		ArrayList<Node> predQ = new ArrayList<Node>();
		HashMap<String, Node> removedNodes = new HashMap<String, Node>();
		ArrayList<Node> V = new ArrayList<Node>();
		ArrayList<Edge> possibleEdges = new ArrayList<Edge>();
		for(Node n : g.getEachNode())
		{
			n.addAttribute("key", 999999999);
			n.addAttribute("pred", n);
			Q.add(n);
		}
		Integer i = 0, j = 0, k = 2000000;
		actualNode = Q.remove(0);
		predQ.add(actualNode);
		Node nextNode = null;
		while(!Q.isEmpty())
		{
			
			//Edge e;
			//removedNodes.put(actualNode.getId(), actualNode);
			for(Node n : Q)
			{
				if(actualNode.hasEdgeBetween(n))
				{
					Edge e = actualNode.getEdgeBetween(n);
					if(Q.contains(n))
					{
						n.setAttribute("key", Math.min((Integer)n.getAttribute("key"), (Integer)e.getAttribute("value")));
						n.setAttribute("pred", actualNode);
					}
				}
					
			}
			Collections.sort(V, new KeyComparator());
			if(!Q.isEmpty())
			{
				nextNode = Q.remove(0);
				predQ.add(nextNode);
				//Node node1 = gPrim.addNode(actualNode.getId());
				//Node node2 = gPrim.addNode(nextNode.getId());
				//gPrim.addEdge(i.toString(), node1, node2);
				actualNode = nextNode;
				//i++;
				//j++;
				//k++;
			}
		}
		for(Node n : predQ)
		{
			Node node1 = gPrim.addNode(n.getId().toString());
		}
		for(Node n : predQ)
		{
			Node pred = n.getAttribute("pred");
			gPrim.addEdge(i.toString(), n.getIndex(), pred.getIndex());
			i++;
		}
		return gPrim;
		
	}
}
